/**
 *  @file FindMinValueAndDel.c
 *  @desc 实现一个双向循环链表的基本插入、删除、查找最小值并删除的操作
 *        特别地，实现了按值查找链表中最小的节点并删除，直到链表为空
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-24 14:31
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ======================== 结构定义 ========================

/**
 * @brief 双向链表节点定义
 * 使用循环链表结构（尾节点指向头节点）
 */
typedef struct node {
    int data;            // 数据域
    struct node *next;   // 后继指针
    struct node *pre;    // 前驱指针
} node, *link;

// ======================== 基础功能函数 ========================

/**
 * @brief 创建一个新节点
 * @param value 节点值
 * @return 成功返回新节点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    newNode->pre = NULL;
    return newNode;
}

/**
 * @brief 初始化链表，创建头节点并构成自环（循环链表）
 * @param head 指向头指针的地址
 */
void initNode(link *head) {
    link newNode = createNode(0);  // 头节点不存储有效数据
    if (newNode == NULL) return;
    *head = newNode;
    (*head)->next = *head;         // 指向自己，形成循环
    (*head)->pre  = *head;
}

/**
 * @brief 打印链表所有元素（跳过头节点）
 * @param head 头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur != head) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ======================== 插入操作 ========================

/**
 * @brief 头插法插入节点（头节点之后）
 * @param head 循环链表头节点
 * @param value 要插入的值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre = head;

    if (head->next != NULL) {
        head->next->pre = newNode;
    }

    head->next = newNode;
}

/**
 * @brief 尾插法插入节点（头节点之前）
 * @param head 循环链表头节点
 * @param value 要插入的值
 */
void istTail(link head, int value) {
    link last = head->pre;  // 当前尾节点
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head;    // 新尾节点指向头
    newNode->pre = last;

    last->next = newNode;
    head->pre = newNode;
}

/**
 * @brief 指定位置插入节点（第 pos 个位置之后）
 * @param head 循环链表头节点
 * @param pos 插入位置（从 1 开始）
 * @param value 插入值
 */
void istByPos(link head, int pos, int value) {
    if (pos < 1) return;
    link cur = head;
    int idx = 1;
    while (cur->next != head && idx < pos) {
        cur = cur->next;
        idx++;
    }
    if (idx != pos) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    if (cur->next != NULL) {
        cur->next->pre = newNode;
    }

    cur->next = newNode;
    newNode->pre = cur;
}

// ======================== 删除操作 ========================

/**
 * @brief 删除指定位置节点
 * @param head 头节点
 * @param pos 要删除的节点位置（从 1 开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == head || pos < 1) return;

    link cur = head->next;
    int idx = 1;

    while (cur != head && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == head) return;  // 越界

    cur->pre->next = cur->next;
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }
    free(cur);
}

// ======================== 特殊功能：查找最小值并删除 ========================

/**
 * @brief 不断查找链表中的最小值节点并删除，直到链表为空
 * @param head 双向循环链表头节点
 */
void findMinValueAndDel(link head) {
    if (head == NULL || head->next == head) return;

    while (head->next != head) {  // 链表不为空
        link cur = head->next;
        link minNode = cur;

        // 找出最小节点
        while (cur != head) {
            if (cur->data < minNode->data) {
                minNode = cur;
            }
            cur = cur->next;
        }

        printf("minValue is %d\n", minNode->data);

        // 删除最小值节点
        minNode->pre->next = minNode->next;
        minNode->next->pre = minNode->pre;

        free(minNode);
    }
}

// ======================== 测试入口 ========================

int main () {
    link head = NULL;
    initNode(&head);  // 初始化链表

    // 插入数据
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    // 查找最小值并删除，直到链表清空
    findMinValueAndDel(head);

    // 打印链表（应为空）
    printList(head);

    return 0;
}
